package sorting;

public class ShellSort {

	public static  <T extends Comparable <? super T>> void sort(T[] data) {

		int size = data.length;

		// 3x+1 increment sequence
		int h = 1;
		while (h < size / 3) {
			h = 3 * h + 1; // 1,4,13,40,121 ...
		}
		
		while (h >= 1) {
			// insertion sort
			// h-sort the array
			for (int index = h; index < size; index++) {
				T key = data[index];
				int position = index;

				while (position > 0 && data[position-1].compareTo(key) > 0) {
					data[position] = data[position-h];
					position--;
				}
				data[position] = key;
			}

			// move to next increments
			h = h/3;
		}
	}
}
